package Leetcode;

/*给你一个非负整数数组 nums ，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。
*/

public class Leetcode45 {

}

class Solution1{	//从后向前查找能跳的最远距离（其他编译器会超时）
	public int jump(int [] nums) {
		int l = nums.length-1, n = 0;
		while(l>0) {	//从后往前依次缩短能跳最远的起跳点的查找
			for(int i=0;i<l;i++) {	//从前往后遍历最后一个起跳点（最少起跳方式一定是包含所有能跳最远的点）
				if(nums[i]+i>=l) {
					l = i;
					n++;
					break;
				}
			}
		}
	}
}

class Solution2{	//从前往后查找能起跳最远的起跳点（每次起跳所能到达的范围都看成下次可能起跳的起跳点）
	public int jump(int [] nums) {
		int n = 0 , end = 0,max = 0;	//n为起跳次数，end为每次起跳所能到达的最远点，max为最远起跳距离
		for(int i=0;i<nums.length-1;i++) {	//遍历起跳点（除去终点）
			max = Math.max(max, nums[i]+i);	//每次遍历更新每次起跳的=所能到达的最远距离
			if(i==end) {	//当遍历到该次起跳所能到达的最远距离时，将下次所有可能的起跳点的范围更新
				end = max;
				n++;
			}
		}return n;
	}
}
